This invention relates to data transformation circuits for transforming an input data value into an output value according to a many-to-one mapping scheme (i.e. such that the same output value may be derived from two or more different input values). Various data transformation methods are described in "Key-to-address transform techniques" by V. Y. Lum, Communications of the ACM, April 1971, page 228.
Such a transformation circuit may be used in an information storage system, for transforming an input data value into a storage address. One such application is described in British Patent Specifications Nos. 1,491,706 and 1,564,563, in which an input data item is hash-coded to produce addresses for a plurality of bit-wide stores, referred to as bit maps. The addressed bits of the bit maps may be set so as to tag the input data item, or alternatively the addressed bits may be read out and combined in an AND gate to determine whether the data item has previously been tagged.
The advantage of using a many-to-one mapping scheme in such a system is that it enables a large but sparsely populated address range to be effectively compressed into a much smaller range, thus reducing the size of the bit maps. However, as explained in those specifications, one problem with such a scheme is that the bit maps may occasionally produce spurious outputs, indicating that a data item has been tagged when in fact it has not. The number of spurious outputs may be reduced for any particular set of data items under consideration, by suitable choice of the transformation. Thus, if a first choice of transformation results in an unacceptably high number of spurious outputs, the hash coder may be modified to produce a different transformation which gives a lower number of spurious outputs.
One object of the present invention is to provide a novel data transformation circuit in which the transformation can readily be modified in a flexible manner.